#include <stdio.h>
#include <stdlib.h>

#define N_MAX 20

// 定义栈结构
typedef struct
{
    int row;
    int col;
} Stack;

int board[N_MAX][N_MAX]; // 棋盘，用于存放皇后位置
int n;                   // 皇后个数
int sulution_count = 0;  //解的个数

Stack stack[N_MAX]; // 栈，用于存放皇后的位置
int top = -1;       // 栈顶指针

// 检查当前位置(row, col)是否可以放置皇后
bool isSafe(int row, int col)
{
    int i, j;

    // 检查当前列是否有皇后
    for (i = 0; i < row; i++)
    {
        if (board[i][col] == 1)
        {
            return false;
        }
    }

    // 检查左上方是否有皇后
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (board[i][j] == 1)
        {
            return false;
        }
    }

    // 检查右上方是否有皇后
    for (i = row, j = col; i >= 0 && j < n; i--, j++)
    {
        if (board[i][j] == 1)
        {
            return false;
        }
    }

    return true;
}

// 回溯函数，用于放置皇后
void solveNQueens()
{
    int row = 0, col = 0;

    while (row < n)
    {
        // 尝试在当前行找到一个可以放置皇后的位置
        while (col < n)
        {
            if (isSafe(row, col))
            {
                board[row][col] = 1;    // 放置皇后
                stack[++top].row = row; // 将皇后位置入栈
                stack[top].col = col;
                col = 0; // 重置列数，继续下一行
                break;
            }
            col++;
        }

        // 如果当前行没有找到可以放置皇后的位置
        if (col == n)
        {
            if (top == -1)
            {
                break; // 栈为空，无解
            }
            else
            {
                // 回溯到上一行，撤销之前放置的皇后
                row = stack[top].row;
                col = stack[top].col + 1;
                board[row][stack[top--].col] = 0;
                continue;
            }
        }

        // 如果已经放置了所有皇后，输出当前解
        if (row == n - 1)
        {
            printf("第%d个解:\n", ++sulution_count);
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    printf("%s ", board[i][j] == 1 ? "♛" : "□");
                }
                printf("\n");
            }
            printf("\n");

            // 继续寻找下一个解
            col = stack[top].col + 1;
            board[stack[top--].row][col - 1] = 0;
            continue;
        }

        row++;
    }
}

int main()
{
    printf("请输入一个数：(4<=n<= 20): ");
    scanf("%d", &n);

    if (n <= 0 || n > 20)
    {
        printf("输入数字出错,请重新输入：4~20\n");
        return 0;
    }

    solveNQueens(); // 解决N皇后问题

    return 0;
}